#include <cstdio>
#include <algorithm>

using namespace std;

void SubArrayForce(int* data, int len)
{
	int left = -1, right = -1;
	int max = -999999;
	for (size_t i = 0; i < len; i++)
	{
		for (size_t j = i; j < len; j++)
		{
			int tmp = 0;
			for (size_t k = i; k <= j; k++)
			{
				tmp += data[k];
			}
			if (tmp > max)
			{
				max = tmp;
				left = i;
				right = j;
			}
		}
	}

	printf("result is :\n");
	for (size_t i = left; i <= right; i++)
	{
		printf("%d+", data[i]);
	}
	printf("=%d\n", max);
}

void SubArrayForceLess(int* data, int len)
{
	int left = -1, right = -1;
	int max = -999999;
	for (size_t i = 0; i < len; i++)
	{
		int tmp = data[i];
		for (size_t j = i + 1; j < len; j++)
		{
			tmp += data[j];
			if (tmp > max)
			{
				max = tmp;
				left = i;
				right = j;
			}
		}
	}

	printf("result is :\n");
	for (size_t i = left; i <= right; i++)
	{
		printf("%d+", data[i]);
	}
	printf("=%d\n", max);
}

void SubArraySlideWindow(int* data, int len)
{
	int max = -999999;
	int sum = 0;

	for (size_t i = 0; i < len; i++)
	{
		sum = std::max(data[i], sum + data[i]);
		max = std::max(max, sum);
	}

	printf("result i = %d\n", max);
}

int main(int argc, char **argv)
{
	int data[] = { 3, -5, 10, -2, 2, -3, 7, -1, 0, 5 };

	//SubArrayForce(data, sizeof(data) / sizeof(data[0]));
	SubArrayForceLess(data, sizeof(data) / sizeof(data[0]));
	SubArraySlideWindow(data, sizeof(data) / sizeof(data[0]));

	return 0;
}